In computing, a graph database uses graph structures with nodes, edges, and associated properties to represent and store data. A graph database provides index-free adjacency. Every element contains a direct pointer to its adjacent elements and no index lookups are necessary. Compared with relational databases, graph databases are often faster for associative data sets, and map more directly to the structure of object-oriented applications. As they depend less on a rigid schema, they are more suitable to manage ad hoc and changing data with evolving schemas.
However, traditional computer architecture requires data to be stored and accessed in sequential order. In order to map the multi-dimensional data of the graph data to the limited dimensionality of existing computer architecture, tradeoffs have to be made with respect to data locality and performance. Additionally, as the graph database becomes larger, it becomes inefficient and often impractical to store the database on a single storage/machine. Efficiently and effectively dividing up graph data for storage in different locations becomes important. Despite efforts to ensure data locality for data of the graph that is likely to be accessed together, often situations arise where processing a graph database query requires access across remote portions of a storage and/or across different storage devices/servers. For example, traversing a graph to locate a desired vertex that is not directly adjacent to a subject vertex but is adjacent to an adjacent intermediary vertex of the subject vertex may take a long time because data of different vertices may be stored in different remote servers/storages. Although this poor performance may be acceptable for infrequent queries, it may be unacceptable for critical and/or frequently utilized queries. Additionally, as types of queries and data stored in the graph database change over time, any optimization needs to be flexible enough to adapt to these changes. Therefore, there exists a need for a flexible and efficient way to improve performance of a graph database.